import org.junit.Test;

public class EditDistance {
	public int editDistance(String s1, String s2){
		if (s1 == null || s2 == null)
			return -1;
		
		if (s1.length() ==0)
			return s2.length();
		
		if (s2.length() == 0)
			return s1.length();
		
		int [][]m = new int[s1.length()+1][s2.length()+1];
		
		for (int i=0; i<m.length; ++i){
			for (int j=0; j<m[0].length; ++j){
				if (i == 0)
					m[i][j] = j;
				else if (j==0)
					m[i][j] = i;
				else{
					if (s1.charAt(i-1) == s2.charAt(j-1))
						m[i][j] = m[i-1][j-1];
					else
						m[i][j] = 1+ Math.min(Math.min(m[i-1][j-1], m[i-1][j]), m[i][j-1]);
				}
			}
		}
		
		return m[s1.length()][s2.length()];
	}
	
	@Test
	public void testResult(){
		EditDistance ed = new EditDistance();
		System.out.println(ed.editDistance("mississippi", "miss"));
	}
}
